This application claims the priority of Korean Patent Application No. 2003-46876, filed on Jul. 10, 2003, in the Korean Intellectual Property Office, the disclosure of which is incorporated herein in its entirety by reference.
1. Field of the Invention
Apparatuses and methods consistent with the present invention relate to error correction decoding, and more particularly, to an error correction decoding method and apparatus, which correct errors included in information data by using error declaration information obtained as a result of decoding the data using a lookup table.
2. Description of the Related Art
In general, an error correction code for a high-density recording system, which is similar to a product code, is constituted by two error correction codes, i.e., an inner code and an outer code. The inner code indicates a horizontal code (N1, K1) in a data block for error correction, and the outer code indicates a vertical code (N2, K2) in the data block. Here, Ni represents the length of an i-th codeword, i.e., an output of an error correction encoder, Ki represents the length of i-th information data, i.e., an input of the error correction encoder, and t represents error correction capability of the error correction code and is obtained by the following equation: t=(Ni−Ki)/2. The product code can be accurate up to 2t erroneous bytes by performing error correction while allowing the inner code and the outer code to exchange erasure information with each other. More specifically, a decoder (not shown) performs a typical decoding process on the inner code (or the outer code) for as many times as the size of a column (or a line) of the inner code (or the outer code) and generates erasure information to be provided to the outer code (or the inner code), i.e., error declaration information that indicates where errors have occurred in a codeword to be decoded. Here, the reason the decoder performs the typical decoding process, rather than an erasure decoding process which guarantees better error correction performance, on the inner code (or the outer code) is that the decoder may not receive the erasure information from the outside. The decoder performs the typical decoding process on the outer code (or the inner code) for as many times as the size of a column (or a line) of the outer code (or the inner code) by using the erasure information received from the inner code (or the outer code) and generates erasure information to be provided to the inner code (or the outer code). Supposing that all of the above decoding processes constitutes one cycle, the decoder performs a predetermined number of cycles of decoding on the inner code and the outer code. If more than a maximum number of errors that can be handled by the inner code (or the outer code) have occurred in the codeword to be decoded, erasure of as many errors as the size of the column of the inner code (or the outer code) is declared. A recording system usually uses a Reed-Solomon code as an error correction code because the Reed-Solomon code has excellent burst error correction capability. Here, burst errors are the most common errors occurring in a recording system.
Erasure information is very important for the Reed-Solomon code because the decoding performance of the Reed-Solomon code can be maximized by simply providing accurate erasure information. However, in a conventional erasure declaring method, erasure of code symbols can be declared even though the code symbols are not erroneous. In other words, in the prior art, a decoding process is performed while allowing an inner code and an outer code of the Reed-Solomon code to exchange inaccurate erasure information with each other, which results in a deterioration in error correction performance of the Reed-Solomon code.
FIG. 1 illustrates a structure of a Reed-Solomon product code (RS-PC), which is a conventional error correction code. Referring to FIG. 1, the RS-PC is comprised of a horizontal code (182, 179) and a vertical code (208, 192). The horizontal code (182, 179), which is referred to as an inner code, can correct 5 to a maximum of 10 erroneous bytes in an erasure decoding process. The vertical code (208, 192), which is referred to as an outer code, can correct 8 erroneous bytes. In the erasure decoding process, the outer code can correct up to 16 erroneous bytes. An RS-PC decoding process is performed in the following manner. Erasure information to be provided to the outer code is generated by performing a decoding process on each row of the inner code 208 times. Thereafter, erasure information to be provided to the inner code is generated by performing an erasure decoding on each column of the outer code 172 times with the use of the erasure information provided when decoding the inner code. Supposing that all of the above decoding processes constitutes one cycle, a predetermined number of cycles of decoding can be performed.
FIGS. 2A and 2B illustrate examples of erasure declarations issued in the RS-PC structure of FIG. 1. More specifically, FIG. 2A illustrates an occasion where six errors have occurred in a first row of the inner code of the RS-PC structure when decoding the RS-PC structure. In FIG. 2A, X indicates the location of each error occurring in the RS-PC structure. If six errors have occurred in the first row of the inner code of the RS-PC structure, a decoder issues a declaration of erasure of the first row of the inner code. In other words, the decoder issues a declaration that all bytes in the first row of the inner code are erroneous, which is inaccurate and then transfers inaccurate error information to the outer code.
FIG. 2B illustrates an occasion where a total of 16 errors have occurred in first three columns of the RS-PC structure in a horizontal direction and a total of 17 errors have occurred in fourth through tenth columns of the RS-PC structure in the horizontal direction. In FIG. 2B, X indicates the location of each error occurring in the RS-PC structure. The decoder generates 17 pieces of erasure information when decoding the inner code of the RS-PC structure and then transfers the 17 pieces of erasure information to the outer code. Since the outer code can only correct up to 16 erroneous bytes, the errors in the first three columns of the RS-PC structure, which could have been successfully corrected if the decoder had been provided accurate erasure information, cannot be corrected. In other words, even errors that fall into an error correction range may not be corrected because of inaccurate erasure information.
FIG. 3 illustrates another structure of a conventional error correction code, i.e., a picket code. Referring to FIG. 3, the picket code extends in a vertical direction and is comprised of a sync code 30, a plurality of long distance codes 31, and a plurality of burst indicator codes 32. Each of the long distance codes 31 and the burst indicator codes 32 is formed based on an RS code. More specifically, each of the burst indicator codes 32 is formed based on RS(62, 30) so as to be able to accurate 16 to a maximum of 32 erroneous bytes in an erasure decoding process. Each of the long distance codes 31 is formed based on RS(248, 216) so as to be able to accurate 16 to a maximum of 32 erroneous bytes in the erasure decoding process. Each of the long distance codes 31 is comprised of information data and parity data, and each of the burst indicator codes 32 is comprised of sector data, control data, and parity data. A method of issuing an erasure declaration in the picket code is as follows. If errors have occurred in the same line of the sync code 30 and a burst indicator code 32, or if errors have occurred in the same line of two different burst indicator codes 32, it is declared that all bytes in the corresponding line are erroneous. Thereafter, an erasure decoding process is performed on each of the long distance codes 31 according to erasure information obtained as a result of the declaration. However, if the erasure information is inaccurate, error correction efficiency may be decreased.
FIG. 4A illustrates an error correction failure that has occurred in a picket code. More specifically, FIG. 4A illustrates an occasion when errors have occurred in the same rows of burst indicator codes 40 and 41 and the number of error lines of each of the burst indicator codes 40 and 41 exceeds 16, a decoder (not shown) declares an error correction failure for the burst indicator codes 40 and 41 and fails to provide any erasure information to a long distance code 42. Therefore, the decoder also declares error correction failure for the long distance code 42, thus decreasing error correction efficiency.
FIG. 4B illustrates an example of an error correction failure that has occurred in a picket code. More specifically, FIG. 4B illustrates an occasion where 32 lines of errors have sporadically occurred in the vicinity of two burst indicator codes 43 and 44 and less than 16 errors have occurred in a long distance code 45. If a decoder (not shown) decodes the long distance code 45 without using pieces of erasure information provided for the burst indicator codes 43 and 44, all the errors, which are less than 16, can be corrected. However, in principle, the picket code is decoded by decoding the long distance code 45 using the pieces of erasure information provided for the burst indicator codes 43 and 44. Therefore, if the number of pieces of the erasure information provided for the burst indicator codes 43 and 44, i.e., detected error information, and the number of errors yet to be detected exceed a maximum number of bytes that can be corrected in the long distance code 45, i.e., 32, the decoder declares an error correction failure.
In short, a deterioration in the performance of a picket code is mainly due to inaccurate erasure information provided to a long distance code by a burst indicator code.
Accordingly, it is necessary to provide accurate erasure information for an RS-PC or a picket code.